package com.le.test;

import org.junit.Test;

import java.util.Arrays;
import java.util.Stack;

/**
 * 小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。
 * 小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住）
 */
public class Code_01_lou {

    public static int[] solution(int[] heights) {
        int[] res = new int[heights.length];

        Stack<Integer> left = new Stack<>();
        // 向左看
        for (int i = 0; i < heights.length; i++) {
            res[i] = left.size();
            while (!left.isEmpty() && left.peek() <= heights[i]){
                left.pop();
            }
            left.push(heights[i]);
        }
        // 向右看
        Stack<Integer> right = new Stack<>();
        for (int i = heights.length - 1; i >= 0; i--) {
            res[i] += right.size() + 1;
            while (!right.isEmpty() && right.peek() <= heights[i]){
                right.pop();
            }
            right.push(heights[i]);
        }
        return res;
    }

    public static int[] solution1(int[] heights) {
        long l = System.currentTimeMillis();
        int[] res = new int[heights.length];
        int index = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0, count = 0; i < heights.length; i++) {
            count++;

            if (i != 0) {
                for (int j = i - 1; j >= 0; j--) {
                    if (stack.isEmpty()) {
                        stack.push(heights[j]);
                    } else {
                        if (stack.peek() < heights[j]) {
                            stack.push(heights[j]);
                        }
                    }
                }
            }
            count += stack.size();
            stack.clear();
            for (int j = i + 1; j < heights.length; j++) {
                if (stack.isEmpty()) {
                    stack.push(heights[j]);
                } else {
                    if (stack.peek() < heights[j]) {
                        stack.push(heights[j]);
                    }
                }
            }
            count += stack.size();
            stack.clear();
            res[index++] = count;
            count = 0;
        }
        System.out.println(System.currentTimeMillis() - l);
        return res;
    }

    @Test
    public void test() {
        int[] arr = {5, 3, 8, 3, 2, 5};
        int[] solution = solution1(arr);
        System.out.println(Arrays.toString(solution));

    }
}
